package mo.tags.stack;

import java.util.Stack;

public class L1081 {


    public String smallestSubsequence(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c-'a']++;
        }
        Stack<Character> stack = new Stack<>();
        boolean[] visited = new boolean[26];
        for (char c : s.toCharArray()) {
            count[c-'a']--;
            if (visited[c-'a']) {
                continue;
            }
            while (!stack.isEmpty() && c < stack.peek() && count[stack.peek()-'a'] > 0) {
                visited[stack.pop()-'a'] = false;
            }
            visited[c-'a'] = true;
            stack.push(c);
        }
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        return builder.reverse().toString();
    }
    
}
